package Leetcode.数组字符串;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName 每日温度
 * @since: 2023/8/28 15:08
 * @auth: kirito
 * @description:
 * 给定一个整数数组 temperatures ，表示每天的温度，
 * 返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，
 * 下一个更高温度出现在几天后。如果气温在这之后都不会升高，
 * 请在该位置用 0 来代替。
 *
 *
 *
 * 示例 1:
 *
 * 输入: temperatures = [73,74,75,71,69,72,76,73]
 * 输出: [1,1,4,2,1,1,0,0]
 * 示例 2:
 *
 * 输入: temperatures = [30,40,50,60]
 * 输出: [1,1,1,0]
 * 示例 3:
 *
 * 输入: temperatures = [30,60,90]
 * 输出: [1,1,0]
 *
 * 题意：给一个数组，找出i位置之后比第一个nums[i]大的相对索引
 * 1.暴力遍历
 * 2.单调栈
 **/
public class 每日温度 {
    /**
     * 算法使用一个栈来存储数组索引，栈中的索引对应的温度值是递减的。
     * 在遍历温度数组时，对于每个温度值，将其索引入栈。如果当前温度大于栈顶索引对应的温度值，
     * 则表示找到了后面第一个比它高的温度，此时可以计算等待天数。
     *
     * 当出现当前温度大于栈顶索引对应的温度值时，循环弹出栈顶索引，
     * 计算等待天数，并将结果存储在结果数组中。这个过程重复进行，
     * 直到栈为空或者当前温度不再大于栈顶索引对应的温度值。
     *
     * 最后，将当前索引入栈，以便在后续的遍历中继续寻找后面第一个比它高的温度。
     *
     * 最后返回结果数组，其中存储了每个温度值后面第一个比它高的温度所需的等待天数
     * @param temperatures
     * @return
     */
//    https://mp.csdn.net/mp_blog/creation/editor/132540528
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length]; // 存储结果的数组，初始值为0
        Deque<Integer> stack = new LinkedList<Integer>(); // 用于存储索引的栈

        // 遍历温度数组
        for (int i = 0; i < length; i++) {
            int temperature = temperatures[i]; // 当前温度
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                // 如果栈非空且当前温度大于栈顶索引对应的温度
                int preIndex = stack.pop(); // 弹出栈顶索引
                ans[preIndex] = i - preIndex; // 计算栈顶索引对应的等待天数
            }
            stack.push(i); // 将当前索引入栈
        }
        return ans; // 返回结果数组
    }
}
